#include "headfiles.h"

using namespace std;

void destroyTree(NODE *root) {
	if (root == NULL) {
		return; 
	}

	stack<NODE *> node_stack;
	stack<int> count_stack;

	node_stack.push(root);
	count_stack.push(0);

	while (!node_stack.empty()) {
		NODE *n = node_stack.top();
		int ref_count = count_stack.top();

		if (ref_count == 0) {
			count_stack.pop();
			count_stack.push(1);

			if (n->left) {
				node_stack.push(n->left);
				count_stack.push(0);
			}
		}
		// ref count is 1, can be deleted
		else {
			node_stack.pop();
			count_stack.pop();
			if (n->right) {
				node_stack.push(n->right);
				count_stack.push(0);
			}
			free(n);
		}
	}
	
	return;
}

